import sortedcontainers


class Solution(object):
    def minTaps(self, n, ranges):
        st = []
        for i in range(n + 1):
            st.append([max(0, i - ranges[i]), min(i + ranges[i], n)])
        st.sort(key=lambda x: (x[0], -x[1]))
        ans = sortedcontainers.SortedList()
        for s, e in st:
            if not ans:
                ans.add(e)
            else:
                start_index = ans.bisect_left(s)
                if start_index == len(ans):
                    return -1
                else:
                    end_index = ans.bisect_right(e)
                    if end_index - start_index >= 2:
                        pop_num = end_index - start_index - 1
                        for _ in range(pop_num):
                            ans.pop(start_index + 1)
                        ans.add(e)
                    else:
                        if end_index == len(ans) and e != ans[-1]:
                            ans.add(e)
        if ans[-1] == n:
            return len(ans)
        return -1


data = Solution()
n = 7
ranges = [1, 2, 1, 0, 2, 1, 0, 1]
print(data.minTaps(n, ranges))
n = 3
ranges = [0, 0, 0, 0]
print(data.minTaps(n, ranges))